package algorithm.leetcode.I101to200;

/**
 * 剑指offer的原题
 * 二分和暴力交替使用
 * 二分法 mid = (H-L)>>1+L 时避免 low = mid
 * 二分法 mid = (H-L+1)>>1+L 时避免 high = mid
 */

public class Q154 {

    public int findMin(int[] nums) {
        int low = 0, high = nums.length-1;

        while (low < high) {
            int mid = ((high-low)>>1) + low;

            // 中间数比左边数要小,说明旋转点在左侧
            if (nums[low] > nums[mid]) high = mid;
            // 中间数比右边数要大,说明旋转点在右侧
            else if (nums[mid] > nums[high]) low = mid+1;
            // 暴力法
            else high--;

        }
        return nums[low];
    }

}
